// 给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。

// 示例:

// 输入: 3
// 输出:
// [
//   [1,null,3,2],
//   [3,2,null,1],
//   [3,1,null,null,2],
//   [2,1,3],
//   [1,null,2,null,3]
// ]
// 解释:
// 以上的输出对应以下 5 种不同结构的二叉搜索树：

//    1         3     3      2      1
//     \       /     /      / \      \
//      3     2     1      1   3      2
//     /     /       \                 \
//    2     1         2                 3

#include <vector>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

/* 
二叉搜索树：左<根<右
1-n 从小到大
整个算法的时间复杂度取决于「可行二叉搜索树的个数」，而对于 n 个点生成的二叉搜索树数量等价于数学上第 n 个「卡特兰数」
空间复杂度一样
*/
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if (n == 0) return {};
        return generateTrees(1, n);
    }
    vector<TreeNode*> generateTrees(int start, int end) {
        if (start > end) return {nullptr};
        vector<TreeNode*> allTrees{};
        // 枚举可行根节点
        for (int i{start}; i <= end; ++i) {
            // 获得所有可行的左子树集合
            vector<TreeNode*> leftTrees = generateTrees(start, i - 1);
            // 获得所有可行的右子树集合
            vector<TreeNode*> rightTrees = generateTrees(i + 1, end);
            // 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
            for (auto& leftTree : leftTrees) {
                for (auto& rightTree : rightTrees) {
                    TreeNode* curTree = new TreeNode(i); // 根节点
                    curTree->left = leftTree;
                    curTree->right = rightTree;
                    allTrees.emplace_back(curTree);
                }
            }
        }
        return allTrees;
    }
};